package com.kele;

import java.util.Arrays;

/**
 * @ClassName : QuickSort
 * @Author : kele
 * @Date: 2022/11/8 21:40
 * @Description : 快排
 */
public class QuickSort {

    /**
     * @param input：输入的数组
     * @param left：左边指针
     * @param right：右指针
     * @return 返回中间位置的下标，且按照数组的基准元素将数组中小于基准的元素放置在基准左边，将大于基准的元素放置在右边
     */
    public static int getMiddle(int[] input, int left, int right) {
        //将数组的第一个元素作为基准元素
        int base = input[left];

        //如果右边指针大于左边指针，循环下去
        while (right > left) {

            while (right > left && input[right] >= base)
                right--;
            input[left] = input[right];

            while (right > left && input[left] <= base)
                left++;
            input[right] = input[left];
        }
        input[left] = base;
        return left;
    }

    public static void sort(int[] intput) {
        int length = intput.length - 1;
        sort(intput, 0, length);
    }

    public static void sort(int[] input, int left, int right) {

        if (right > left) {
            int middle = getMiddle(input, left, right);
            sort(input, left, middle - 1);
            sort(input, middle + 1, right);
        }
    }

    public static void main(String[] args) {

        int[] input = {5, 5, 8, 2, 6, 2, 9, 8, 1, 7, 3, 0, 4};
        sort(input);
        System.out.println(Arrays.toString(input));

    }

}
